<!DOCTYPE html>
<html lang="zh-cn">
<head>
	
	<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
	<title>
Levenshtein distance（编辑距离）算法 | 
穷折腾</title>
	<link rel="stylesheet" href="/static/css/style.css" />
	<link rel="stylesheet" href="/static/css/pygments.css" />
	<link rel="alternate" type="application/rss+xml" title="RSS" href="http://blog.zorro.im/rss.xml" />
	<link rel="icon" type="image/png" href="/static/img/favicon.png">
</head>
<body>
    <div id="container">
      <div id="main" role="main">
        <header>
		<h1>
Levenshtein distance（编辑距离）算法
</h1>
		</header>

     <nav>
		<span><a title="home page" class="" href="/">home</a></span>
		<span><a title="标签" class="" href="/tags/index.html">标签</a></span>
		<span><a title="订阅" class="" href="/rss.xml">订阅</a></span>
        <span><a href="/posts/about.html" title="关于">关于</a></span>
     </nav>

     <article class="content">
        <section class="post">
            
		<p>在用Git的时候，如果一不小心把命令参数输入错了，比如把<code>show</code>写成了<code>slow</code>，Git会进行有好的提示：</p>
<div class="codehilite"><pre><span class="nv">$git</span> slow
git: <span class="s1">&#39;slow&#39;</span> is not a git command. See <span class="s1">&#39;git --help&#39;</span>.

Did you mean this?
    show
</pre></div>


<p>一直很好奇这是基于什么算法找出来的相思结果，Google了一番，发现了一个NB的算法——Levenshtein distance，中文名叫“编辑距离”。关于这个算法的具体信息，可以参照<a href="http://en.wikipedia.org/wiki/Levenshtein_distance">维基百科</a>。在这我就做个概述。</p>
<p>这个算法是用来计算两个字符串之间的不同的，就是把一个字符串A通过一些列变换（插入、删除、替换）得到字符串B的最少步骤。可以用来做拼写检查、DNA匹配等。</p>
<p>算法的基本原理就是中学时代就学过的动态规划。（太久没有接触数学了，遇到这个问题时还去查了很久的动态规划。。。）</p>
<p>这个算法的巧妙之处（至少是我认为）是用了一个矩阵来辅助计算。当时看到这个矩阵的时候深深地被震撼到了，看了两天愣是没弄明白。一开始打算找点汉语资料研究一下，结果发现网上的都是半吊子货，于是重新拾起Wikipedia，硬着头皮终于弄明白了。</p>
<p>鉴于解释这个算法需要画图，我也没个好用的工具，就放弃了。如果不明白，强烈建议看Wikipedia。结合推导公式和矩阵图，应该不难明白。</p>
<p>有个外国哥们基于这个算法又改进了一下，在原有的三种操作（插入、删除、替换）中又增加了一种“交换”，这对于拼写检查之类的还是很有用的。这种改进后的算法又叫<a href="http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance">Damerau–Levenshtein distance</a>。Git源码里就是采用的这种算法，具体代码可以查看<a href="https://github.com/git/git/blob/master/levenshtein.c">这里</a>。需要注意的是，Git中把4中操作都加上了权值，这样更灵活一些。</p>
<p>为了更好的理解这个算法，我自己也基于Python实现了一下，代码放在了Gist上，可以访问<a href="https://gist.github.com/zqqf16/6137789">这里</a>。PS：只是为了描述一下算法，并没有过多地考虑效率问题。</p>
	</section>
	<section class="meta">
		<span class="tags">Tagged by 
			<a href="/tags/Levenshtein distance.html">Levenshtein distance</a>
		</span>

		<span class="time">&nbsp;<time datetime="2013-08-02">2013-08-02</time></span>
	</section>
	<!-- Duoshuo Comment BEGIN -->
<div class="ds-thread"></div>
<script type="text/javascript">
	var duoshuoQuery = {short_name:"zqqf16"};
	(function() {
		var ds = document.createElement('script');
		ds.type = 'text/javascript';ds.async = true;
		ds.src = 'http://static.duoshuo.com/embed.js';
		ds.charset = 'UTF-8';
		(document.getElementsByTagName('head')[0] 
		|| document.getElementsByTagName('body')[0]).appendChild(ds);
	})();
</script>
<!-- Duoshuo Comment END -->

<hr/>


        </section>
     </article>
	 <div id="copy">&copy; Powered by <a href="https://github.com/zqqf16/zqqf16.github.com" title="Peanut">Peanut</a> | Themed by <a href="http://lhzhang.com" title="sext ii">sext ii</a></div>
      </div>
    </div> <!--! end of #container -->
	<script>
  		(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  			(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  		 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  			})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  		ga('create', 'UA-41282906-2', 'zorro.im');
  		ga('send', 'pageview');
	</script>
</body>
</html>
